package LimitedTimeGame.Day_0207;

/**
 * @author zxc
 * @date 2023/02/07 09:51
 **/

import java.util.Arrays;

/**
 * 题目 ：矩阵中距离
 * 题目详述 ：
 * 给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 * 两个相邻元素间的距离为 1 。
 *
 * 提示：
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 104
 * 1 <= m * n <= 104
 * mat[i][j] is either 0 or 1.
 * mat 中至少有一个 0
 *
 */
public class UpdateMatrix {
    /**
     * 思路 ：
     *
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {
        int len = mat.length;
        int col = mat[0].length;
        int[][] dp = new int[len][col];
        for (int[] ints : dp) {
            Arrays.fill(ints , len + col);
        }
        // 初始化
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < col ; j++){
                if(mat[i][j] == 0){
                    dp[i][j] = 0;
                }
            }
        }
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < col ; j++){
                if(dp[i][j] == 0){
                    if(i + 1 < len && dp[i + 1][j] == len + col){
                        dp[i + 1][j] = 1;
                    }
                    if(i - 1 >= 0 && dp[i - 1][j] == len + col){
                        dp[i - 1][j] = 1;
                    }
                    if(j - 1 >=0 && dp[i][j - 1] == len + col){
                        dp[i][j - 1] = 1;
                    }
                    if(j + 1 < col && dp[i][j + 1] == len + col){
                        dp[i][j + 1] = 1;
                    }
                }
            }
        }
        while(true){
            if (allFill(dp)){
                break;
            }
            else {
                fillDp(dp);
            }
        }
        return dp;
    }

    private void fillDp(int[][] dp) {
        int len = dp.length;
        int col = dp[0].length;
        for(int i = 0 ; i < dp.length ; i++){
            for(int j = 0; j < dp[i].length ; j++){
                int flag = 0;
                int target = 0;
                if(dp[i][j] == len + col){
                    if(i + 1 < dp.length){
                        target++;
                        if(dp[i + 1][j] != len + col){
                            dp[i][j] = Math.min(dp[i][j] , dp[i + 1][j] + 1);
                            flag++;
                        }
                    }
                    if(i - 1 >= 0){
                        target++;
                        if(dp[i - 1][j] != len + col){
                            dp[i][j] = Math.min(dp[i][j] , dp[i - 1][j] + 1);
                            flag++;
                        }
                    }
                    if(j - 1 >= 0){
                        target++;
                        if(dp[i][j - 1] != len + col){
                            dp[i][j] = Math.min(dp[i][j] , dp[i][j - 1] + 1);
                        }
                    }
                    if(j + 1 < dp[0].length){
                        target++;
                        if(dp[i][j + 1] != len + col) {
                            dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                            flag++;
                        }
                    }
                }
                if(flag < target){
                    dp[i][j] = len + col;
                }
            }
        }
    }

    private boolean allFill(int[][] dp) {
        int len = dp.length;
        int col = dp[0].length;
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < col ; j++){
                if(dp[i][j] == len + col){
                    return false;
                }
            }
        }
        return true;
    }
}
